package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T115 {
    public static void main(String[] args) {
        System.out.println(new T115().numDistinct("babgbag", "bag"));
        System.out.println(new T115().numDistinct2("babgbag", "bag"));
    }

    public int numDistinct2(String s, String t) {
        int sLen = s.length() + 1;
        int tLen = t.length() + 1;
        int[][] dp = new int[sLen][tLen];
        for (int i = 0; i < sLen; i++) {
            for (int j = 0; j < tLen; j++) {
                if (j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                if (i == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[sLen - 1][tLen - 1];
    }

    //输入：s = "rabbbit", t = "rabbit"
    //输出：3
    //解释：
    //如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。

    public int numDistinct(String s, String t) {
        int sLen = s.length() - 1;
        int tLen = t.length() - 1;
        int[][] dp = new int[sLen + 1][tLen + 1];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }
        return process(s, t, sLen, tLen, dp);
    }

    //s = "rabbbit", t = "rabbit"
    private int process(String s, String t, int i, int j, int[][] dp) {
        if (j < 0) {
            return 1;
        }
        if (i < 0) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        char sChar = s.charAt(i);
        char tChar = t.charAt(j);
        int ans = -1;
        if (sChar == tChar) {
            ans = process(s, t, i - 1, j - 1, dp) + process(s, t, i - 1, j, dp);
        } else {
            ans = process(s, t, i - 1, j, dp);
        }
        dp[i][j] = ans;
        return ans;
    }
}
